package leetcode_top;
import java.util.*;
import org.junit.*;
public class Ex140 {

    class Solution1 {
        public List<String> wordBreak(String s, List<String> wordDict) {
            len = s.length();
            set = new HashSet<>(wordDict);
            dfs(0, "", s);
            return res;
        }
        int len;
        List<String> res = new ArrayList<>();
        Set<String> set;
        public void dfs(int idx, String cur, String s) {
            if (idx == len) {
                res.add(cur);
                return;
            }
            String str = "";
            for (int i = idx; i < len; i++) {
                str = s.substring(idx, i + 1);
                if (set.contains(str)) {
                    dfs(i + 1, cur + " " + str, s);
                }
            }
        }
    }
    class Solution {
        public List<String> wordBreak(String s, List<String> wordDict) {
            len = s.length();
            set = new HashSet<>(wordDict);
            boolean[] f = new boolean[len + 1 ]; //f[i]表示s[0:i]是不是一个可以拆分为wordDict中词语的单词
            f[0] = true; //认为f[0]表示空串，为了可行让她为true
            String str;
            for (int i = 1; i < len; i++) { //遍历右边界
                for (int j = i; j > 0; j--) { //遍历左边界
                    str = s.substring(j, i + 1);
                    if (f[j - 1] && set.contains(str)) {
                        f[j] = true;
                        break;
                    }
                }
            }
            return null;
        }
        int len;
        List<String> res = new ArrayList<>();
        Set<String> set;
        public void dfs(int idx, String cur, String s) {
            if (idx == len) {
                res.add(cur);
                return;
            }
            String str = "";
            for (int i = idx; i < len; i++) {
                str = s.substring(idx, i + 1);
                if (set.contains(str)) {
                    dfs(i + 1, cur + " " + str, s);
                }
            }
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        List<String> w = new ArrayList<>();
        // Collections.addAll(w, "cat", "cats", "and", "sand", "dog");
        Collections.addAll(w, "apple", "pen", "applepen", "pine", "pineapple");

        // System.out.println(s.wordBreak("catsanddog", w));
        System.out.println(s.wordBreak("pineapplepenapple", w));

    }
}
